package lc20240607;

import java.util.*;

/**
  * @description 单词搜索II 字典树+回溯算法
  * @author 不知名帅哥
  * @date 2024/6/7 23:10
  * @version 1.0
*/
public class WordSearchII {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> result = new HashSet<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, trie.root, i, j, result, visited);
            }
        }

        return new ArrayList<>(result);
    }

    private void dfs(char[][] board, TrieNode node, int i, int j, Set<String> result, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j]) {
            return;
        }

        char c = board[i][j];
        TrieNode child = node.children.get(c);
        if (child == null) {
            return;
        }

        if (child.word != null) {
            result.add(child.word);
            child.word = null; // 避免重复添加
        }

        visited[i][j] = true;
        for (int[] direction : DIRECTIONS) {
            int newI = i + direction[0];
            int newJ = j + direction[1];
            dfs(board, child, newI, newJ, result, visited);
        }
        visited[i][j] = false;
    }

    public static void main(String[] args) {
        WordSearchII ws = new WordSearchII();
        char[][] board = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(ws.findWords(board, words));
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word = null;
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        node.word = word;
    }
}
